package daily.oct;

import java.util.Arrays;

public class lc2300 {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        // 只需要对potions排序，spells保持原顺序
        Arrays.sort(potions);
        int[] result = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            // 对每个spell，在排序后的potions中二分查找第一个满足条件的索引
            int count = binarySearch(spells[i], potions, success);
            result[i] = count;
        }

        return result;
    }

    public int binarySearch(int spell, int[] potions, long target) {
        int left = 0;
        int right = potions.length - 1;

        // 二分查找第一个满足 spell * potion >= target 的索引
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long product = (long) spell * potions[mid];

            if (product >= target) {
                right = mid - 1; // 尝试找到更小的满足条件的索引
            } else {
                left = mid + 1;
            }
        }

        // left是第一个满足条件的索引，从left到末尾都满足条件
        return potions.length - left;
    }

    public static void main(String[] args) {
        lc2300 lc = new lc2300();
        int[] spells1 = {5, 1, 3};
        int[] potions1 = {1, 2, 3, 4, 5};
        int success1 = 7;
        int[] result1 = lc.successfulPairs(spells1, potions1, success1);
        System.out.println(Arrays.toString(result1)); // 输出: [4, 0, 3]

        int[] spells2 = {3, 1, 2};
        int[] potions2 = {8,5,8};
        int success2 = 16;
        int[] result2 = lc.successfulPairs(spells2, potions2, success2);
        System.out.println(Arrays.toString(result2));
    }
}
